#include "jump.h"
int jump(std::vector<int> &nums) {
    int start = 0;
    int end = 1;
    int min_jump = 0;
    int maxPos = 0;
    while (end < nums.size()) {
        for (int i = start; i < end; i++) {
            maxPos = std::max(maxPos, i + nums[i]); // 找到能走到的最大位置
        }
        start = end;
        end = maxPos + 1;
        min_jump++;
    }
    return min_jump;
}
bool dfsJump(std::vector<int> &arr, int start, std::vector<bool> &visited) {

    if (start >= arr.size() || start < 0 || visited[start]) {
        return false;
    } else if (arr[start] == 0) {
        return true;
    } else {
        visited[start] = true;
        return dfsJump(arr, start + arr[start], visited) ||
               dfsJump(arr, start - arr[start], visited);
    }
}
bool canReach(std::vector<int> &arr, int start) {
    std::vector<bool> visited = std::vector<bool>(arr.size(), false);
    return dfsJump(arr, start, visited);
}
int maxResultOpt(std::vector<int> &nums, int k) {
    const int n = nums.size();
    std::vector<int> dp = std::vector<int>(n, 0);
    dp[0] = nums[0];
    int min;
    for (int i = 1; i < n; i++) {
        min = std::numeric_limits<int>::min();
        for (int c = 1; c <= k; c++) {
            if (i - c >= 0) {
                min = std::max(dp[i - c], min);
            }
        }
        dp[i] =
            min == std::numeric_limits<int>::min() ? nums[i] : min + nums[i];
    }
    return dp[n - 1];
}

int maxResult(std::vector<int> &nums, int k) {
    const int n = nums.size();
    std::deque<std::pair<int, int>> queue;
    queue.emplace_back(nums[0], 0);
    int result = nums[0];
    for (int i = 1; i < n; i++) {
        // i 之前的1-k个位置可访问，超过范围之后队列头数据不影响值的更新，删除
        while (i - queue.front().second > k) {
            queue.pop_front();
        }
        result = queue.front().first + nums[i];
        // 如果更新的值比队列尾部元素大，这时候pop数据保证队列元素是递增的
        while (!queue.empty() && result >= queue.back().first) {
            queue.pop_back();
        }
        queue.emplace_back(result, i);
    }
    return result;
}
